package sorting2;

public class QuickSort {

	public int[] quickSort(int[] array, int comecoDoArray, int fimDoArray){

		if (comecoDoArray >= fimDoArray){
			return array;
		}

		int indiceDoPivo = particion(array, comecoDoArray, fimDoArray);
		quickSort(array, comecoDoArray, indiceDoPivo-1);
		quickSort(array, indiceDoPivo+1, fimDoArray);
		return array;
	}

	private int particion(int[] array, int comecoDoArray, int fimDoArray){
		int i = comecoDoArray + 1;
		int j = fimDoArray; 
		int p = array[comecoDoArray];

		while (i <= j){
			if (array[i] <= p){
				i++;
			} else if (array[j] > p){
				j --;
			} else {
				array = swap(array, i, j);
			}
		}

		array = swap(array, comecoDoArray, i-1);
		return i-1;
	}

	private int[] swap(int[] array, int menor, int maior){
		int temporario = array[maior];
		array[maior] = array[menor];
		array[menor] = temporario;

		return array;

	}
}